# -*- encoding: UTF-8 -*-
'''
@File    :  quickselect.py
@Time    :  2021/05/16 15:48:14
@Author  :  Kearney
@Contact :  191615342@qq.com
@Desc    :  快速选择算法
'''


def qselect(A, k):
    """
    返回TopK小的数组
    第K小的数字 = max(qseletc(A,k))，A中不许有重复值"""
    if len(A) <= k:
        return A
    pivot = A[-1]
    left = [pivot] + [x for x in A[:-1] if x < pivot]
    llen = len(left)
    if llen == k:
        return left
    if llen > k:
        return qselect(left, k)
    else:
        right = [x for x in A[:-1] if x >= pivot]
        return left + qselect(right, k - llen)


unsort = [4, 2, 1, 7, 4, 3]
print(max(qselect(unsort, 3)))
